#include "stdio.h"
#include "stdlib.h"

typedef int ElemType;
typedef struct DuLNode {
	ElemType data;
	struct DuLNode* prior,*next;  //前结点指针和后结点指针
}DuLNode, *DuLinkList;

//初始化链表
void InitDuLinkList(DuLinkList& L) {
	L = (DuLinkList)malloc(sizeof(DuLNode));  //创建头结点
	L->next = L->prior = L;  //前结点指针和后节点指针指向自己
}

//查找指定位置的元素
DuLinkList LocationElem(DuLinkList L, int i) {
	DuLinkList P = L;  //P指向头结点
	int j = 1;
	while (P && j <= i) {
		P = P->next;
		j++;
	}
	return P;
}

//插入结点
void ListInsert_Dul(DuLinkList& L,int i, ElemType e ) {
	//创建结点
	DuLinkList P = (DuLinkList)malloc(sizeof(DuLNode));
	DuLinkList Q = LocationElem(L, i - 1);
	P->data = e;
	P->next = Q->next;
	Q->next->prior = P;
	Q->next = P;
	Q->prior = L;
}

//删除结点
void ListDelete_Dul(DuLinkList& L, int i, ElemType& e) {
	DuLinkList Q = LocationElem(L, i - 1);
	DuLinkList P = Q->next;
	e = P->data;
	Q->next = P->next;
	P->next->prior = Q;
	free(P);
}

//打印链表
void Print_Dul(DuLinkList L) {
	DuLinkList P = L->next;  //指向第一个节点
	while (P != L) {
		printf("%3d", P->data);
		P = P->next;
	}
	printf("\n");
}

int main() {
	DuLinkList L;  //创建双向链表
	ElemType e;  //接收删除的元素
	InitDuLinkList(L);  //初始化链表
	ListInsert_Dul(L, 1, 4);
	ListInsert_Dul(L, 1, 3);
	ListInsert_Dul(L, 1, 2);
	ListInsert_Dul(L, 3, 1);
	Print_Dul(L);
	ListDelete_Dul(L, 2, e);
	printf("删除元素为%d\n", e);
	Print_Dul(L);
	ListDelete_Dul(L, 3, e);
	printf("删除元素为%d\n", e);
	Print_Dul(L);
	return 0;
}